#include<stdio.h>
#include<stdlib.h>
/**
 * 看着像计数排序，但是也并不是直接hash
 * 确实是一种更加巧妙的方法，节省了空间，这个算法只需要和数组大小等长的两个数组的辅助空间
 * 而hash的话，需要的最大值和最小值差值长度的空间(会出现极端情况，且最后输出遍历会比较耗时)
 * 
 * @param a 待排序数组
 * @param b 辅助数组
 * @param n a的长度（也是b的长度）
 * @return void
 */
void cmpCountSort(int a[],int b[],int n){
    int i,j,*count;//count是数组
    count=(int*) malloc(sizeof(int)*n);
    for(i=0;i<n;i++){ //初始化count数组，元素全为0
        count[i]=0;
    }
    for(i=0;i<n-1;i++){//从第1个元素遍历到倒数第二个
        for(j=i+1;j<n;j++){//从第二个遍历到最后一个
        //两个数字，较大的那个下标会被记录下来,那么最大的那个数字，被记录的次数也一定是最多的
        //一次类推，因为这些数字都是会被挨个比较的，count里面对应下标元素，加1的次数也就对应
        //这个元素“有多大的程度”
            if(a[i]<a[j]) count[j]++;
            else count[i]++;
        }
    }
    //这里赋值是根据次数赋值，所以次数大（值大的）的在右边，次数小（值小的）的在左边
    //但是如何保证相同次数的呢？
    //这里如果次数相同就意味着这两个数相同？不是的，可以用3，3，3这个数组验证，他们的count结果是2，1，0
    //可以看出来，虽然排序没有重复的问题，但是我相同的元素顺序颠倒了，可以上面那个
    //            if(a[i]<a[j]) count[j]++; 加上<= ，那么就不会出现颠倒的情况了
    for(i=0;i<n;i++){
        b[count[i]]=a[i];
    }
    free(count);

}
/**
 * 总结如下：
 * （1）b的结果为-10 10 11 19 25 25
 * （2）实际上是n个元素中，两两比较，即从n个数字任选2个，C_n^2 = n(n-1)/2
 *  (3)不是稳定的，算法会将两个相同的元素点到为止，靠前的排序后更加靠后，
 *     要将if中的小于改成小于等于
 */
int main(void){
    int a[]={25,-10,25,10,11,19};
    int b[6];
    cmpCountSort(a,b,6);
    for(int i=0;i<6;i++){
        printf("%d ",b[i]);
    }
}